# 	Q9_197. 排列序号 (数学题)
# 给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始
# 例1：
# 输入:[1,2,4]
# 输出:1
# 例 2:
# 输入:[3,2,1]
# 输出:6
# 思路：
# •	要知道排列元素的所有排列按字典序排序后该排列的编号，可以通过求出小于这个排列的排列组合的数量num，那么答案就是num+1。
# •	我们从第1位开始向后依次考虑，以[4,3,2,1]为例：
# •	第1位：可选取的元素(3,2,1)小于第1位的元素有3个。假如我们固定第1位小于4的情况，那么第一位有3种，后面3位的排列组合数有3! 种，所以比较到第1位就小于该排列的排列组合数共有3*3!=18种。
# •	第2位：固定第1位为4，那么小于第2位的元素(‘3’)有2个：可选取元素(2,1)。后面2位的排列组合数有2! 种，所以比较到第2位才小于该排列的排列组合数共有2*2!=4种。
# •	第三位：固定第2位为3，那么可选取的元素(1)小于第3位的元素有1个。后面1位的排列组合数有1!种，所以比较到第3位才小于该排列的排列组合数共有1*1!=1种。
# •	第四位：没有选择余地。
# •	所以答案为18+4+1+1=24
# •	综上所述，假设排列有n个元素，且用cnt[i]表示小于第i位的元素个数，我们可以得到答案为：
# 复杂度：
# •	假设排列长度为n；
# •	常数级别的复杂度，空间复杂度O(1)；
# •	依次处理的复杂度为O(n)，每次处理求剩余可选择比自己小的最坏复杂度为O(n)，最坏时间复杂度为O(n^2)。

class Solution:
    # 法1：正向思维
    def permutationIndex(self, A):
        index = 1  # 至少为1，初始的全排列为增序，index记录第几个全排列
        for i in range(len(A)):
            n_smaller = 0  # 后面有几个比它小的数字
            factor = 1  # factor用来计算阶乘的权值
            for j in range(i + 1, len(A)):
                if A[j] < A[i]: n_smaller += 1
            if n_smaller > 0:
                for k in range(1, len(A) - i):
                    factor *= k
            index = (factor * n_smaller) + index
        return index

    # 法2：逆向思维
    def permutationIndex2(self, A):
        n, factorial, idx = len(A), 1, 0
        # 求出剩余可选择元素中小于自身的元素个数
        for i in reversed(range(n)):  # 应该从低位到高位数
            n_smaller = 0
            for j in range(i + 1, n):
                if A[j] < A[i]: n_smaller += 1
            idx += n_smaller * factorial
            factorial *= (n - i)
        return idx + 1
